package org.laizili.solution.nowcodertop101.bitree;

import org.laizili.structure.tree.bitree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://www.nowcoder.com/practice/8daa4dff9e36409abba2adbe413d6fae?tpId=295&sfm=html&channel=nowcoder">BM35 判断是不是完全二叉树</a>
 * <p>
 * tags: 二叉树; 层序遍历
 * </p>
 * <p>
 * Notes: 完全二叉树性质; 空指针结点入队问题；
 * </p>
 */
public class BM35 {
    private static class Solution {
        public boolean isCompleteTree(TreeNode root) {
            if (root == null)
                return true;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            TreeNode cur;
            boolean notComplete = false;
            while (!queue.isEmpty()) {
                cur = queue.poll();
                if (cur == null) {
                    notComplete = true;
                    continue;
                }
                if (notComplete)
                    return false;
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
            return true;
        }
    }
}
